package a4_p04_ak_fh;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedMultigraph;

import a2_p04_ak_fh.AttVertex;

public class Fleury {
	private long time = 0;
	private int hits = 0;
	private double weightsum = 0.0;
	private List<AttVertex> eulerkreis = new ArrayList<AttVertex>();
	private Fleury(WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		CalcEulerCirc(graph);
	}

	public long getTimeInMillis() {
		return this.time;
	}

	public long getTimeInSec() {
		return this.time / 100;
	}

	public int getHits() {
		return this.hits;
	}

	public double getWeightSum() {
		return this.weightsum;
	}
	public List<AttVertex> getEulerWay(){
		return this.eulerkreis;
	}
	public static Fleury Calc(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		return new Fleury(graph);
	}
	private boolean vertexGradIsEven(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph,
			AttVertex vertex) {
		int sum = 0;
		for (DefaultWeightedEdge edge : graph.edgesOf(vertex)) {
			sum++;
		}
		return (sum % 2 == 0);
	}

	private boolean checkGraphVertices(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		for (AttVertex vertex : graph.vertexSet()) {
			if (!vertexGradIsEven(graph, vertex))
				return false;
		}
		return true;
	}

	/**
	 * Zusammenhaegend und nur Knoten mit gerden Kantenanzahl
	 * 
	 * @return
	 */
	private boolean checkPrecondtion(
			WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		if (graph instanceof UndirectedGraph) {
			ConnectivityInspector<AttVertex, DefaultWeightedEdge> connectedgraph = new ConnectivityInspector<AttVertex, DefaultWeightedEdge>(
					(UndirectedGraph<AttVertex, DefaultWeightedEdge>) graph);
			return (connectedgraph.isGraphConnected() && checkGraphVertices(graph));
		} else
			return false;
	}
	private WeightedGraph<AttVertex, DefaultWeightedEdge> copyOfGraph(WeightedGraph<AttVertex, DefaultWeightedEdge> graph){
		WeightedGraph<AttVertex, DefaultWeightedEdge> copyGraph = new WeightedMultigraph<AttVertex, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		
		for (DefaultWeightedEdge edge : graph.edgeSet()) {
			copyGraph.addVertex(graph.getEdgeSource(edge));
			copyGraph.addVertex(graph.getEdgeTarget(edge));
			copyGraph.addEdge(graph.getEdgeSource(edge), graph.getEdgeTarget(edge), edge);
		}
		return copyGraph;
	}
	private AttVertex nextVertex(WeightedGraph<AttVertex, DefaultWeightedEdge> graph,AttVertex vertex){
		WeightedGraph<AttVertex, DefaultWeightedEdge> testgraph = copyOfGraph(graph);
		for (DefaultWeightedEdge edge : graph.edgesOf(vertex)) {
			if(graph.getEdgeSource(edge).equals(vertex)){
				if(graph.edgesOf(graph.getEdgeTarget(edge)).size()>1){
					testgraph.removeEdge(edge);
					if(testgraph.edgesOf(vertex).size()==0)
						testgraph.removeVertex(vertex);
					if (graph instanceof UndirectedGraph) {
						ConnectivityInspector<AttVertex, DefaultWeightedEdge> connectedgraph = new ConnectivityInspector<AttVertex, DefaultWeightedEdge>(
								(UndirectedGraph<AttVertex, DefaultWeightedEdge>) testgraph);
						if(connectedgraph.isGraphConnected())
							return graph.getEdgeTarget(edge);
					}
						
					
				}
					
			}else{
				if(graph.edgesOf(graph.getEdgeSource(edge)).size()>1){
					testgraph.removeEdge(edge);
					if(testgraph.edgesOf(vertex).size()==0)
						testgraph.removeVertex(vertex);
					if (graph instanceof UndirectedGraph) {
						ConnectivityInspector<AttVertex, DefaultWeightedEdge> connectedgraph = new ConnectivityInspector<AttVertex, DefaultWeightedEdge>(
								(UndirectedGraph<AttVertex, DefaultWeightedEdge>) testgraph);
						if(connectedgraph.isGraphConnected())
							return graph.getEdgeSource(edge);
					}
				}
					
			}
			testgraph = copyOfGraph(graph);
		}
		return null;
	}
	private void CalcEulerCirc(WeightedGraph<AttVertex, DefaultWeightedEdge> graph) {
		if(checkPrecondtion(graph)){
		WeightedGraph<AttVertex, DefaultWeightedEdge> cleargraph = copyOfGraph(graph);
		List<AttVertex> unterGraphVertexList = new ArrayList<AttVertex>();
		this.time = System.currentTimeMillis();
		AttVertex nextVertex = (AttVertex) (graph.vertexSet().toArray())[0];
		unterGraphVertexList.add(nextVertex);
		AttVertex vertex = null;
		AttVertex startVertex = nextVertex;
		
		while(cleargraph.edgeSet().size()!=1) {
			vertex = nextVertex(cleargraph,nextVertex);
			unterGraphVertexList.add(vertex);
			cleargraph.removeEdge(nextVertex, vertex);
			this.hits++;
			if(cleargraph.edgesOf(nextVertex).size()==0){
				cleargraph.removeVertex(nextVertex);
			}
			nextVertex = vertex;
		}
		if(cleargraph.getEdge(nextVertex, startVertex)!=null){
			unterGraphVertexList.add(startVertex);
		}else{
			System.out.println("FEHLER! letzte Kante ist nicht die Schlusskante zum Eulerkreis!!!");
		}
		
		this.eulerkreis = unterGraphVertexList;
		this.time = System.currentTimeMillis()-this.time;
		System.out.println(eulerkreis);
		
		}else
			System.out.println("Graph besitzt keinen Eulerkreis");
	}
}
